Proof of the 1-factorization and Hamilton decomposition conjectures III: approximate decompositions

摘要

In a sequence of four papers, we prove the following results (via a unifiedapproach) for all sufficiently large $n$: (i) [1-factorization conjecture] Suppose that $n$ is even and $D\geq 2\lceiln/4\rceil -1$. Then every $D$-regular graph $G$ on $n$ vertices has adecomposition into perfect matchings. Equivalently, $\chi'(G)=D$. (ii) [Hamilton decomposition conjecture] Suppose that $D \ge \lfloor n/2\rfloor $. Then every $D$-regular graph $G$ on $n$ vertices has a decompositioninto Hamilton cycles and at most one perfect matching. (iii) We prove an optimal result on the number of edge-disjoint Hamiltoncycles in a graph of given minimum degree. According to Dirac, (i) was first raised in the 1950s. (ii) and (iii) answerquestions of Nash-Williams from 1970. The above bounds are best possible. Inthe current paper, we show the following: suppose that $G$ is close to acomplete balanced bipartite graph or to the union of two cliques of equal size.If we are given a suitable set of path systems which cover a set of`exceptional' vertices and edges of $G$, then we can extend these path systemsinto an approximate decomposition of $G$ into Hamilton cycles (or perfectmatchings if appropriate).